/*
Source : https://leetcode.com/problems/letter-combinations-of-a-phone-number/
Author : nflush@outlook.com
Date   : 2016-08-23
*/

/*
17. Letter Combinations of a Phone Number

    Total Accepted: 93583
    Total Submissions: 309481
    Difficulty: Medium

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want. 
*/
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        char asn[digits.size() + 1] = {0};
        vector<string> ret;
        if(digits.size())
            letterCombinations_hlepper(asn, ret, digits, 0);
        return std::move(ret);
    }
private:
    void letterCombinations_hlepper(char a[], vector<string> &ret, string &digits, int index) {
        if (index == digits.size()){
            ret.push_back(string(a));
            return;
        }
        char ch = digits[index];
        if (ch <= '1' || ch > '9'){
            return;
        }
        for (int i =0; m_map[ch - '2'][i] != '\0'; i++){
            a[index] = m_map[ch - '2'][i];
            letterCombinations_hlepper(a, ret, digits, index +1);
        }
    }
    const char m_map[8][5] = {
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };
};
